1. Field of the Invention
The present invention relates to a variable length encoding system used for coding a moving picture.
2. Description of Related Art
As a technology for coding an image data at a high efficiency, a combined system composed of a DCT (discrete cosine transformation) and a variable length coding has been standardized and widely used. However, when the pixel rate of an image to be processed is high, a processing based on a software is not sufficient in processing velocity, and a dedicated hardware becomes necessary. In addition, since a variable length code (VLC) table is used for the variable length coding, a large memory becomes necessary.
As a system intended for realizing a high speed processing, for example, Japanese Patent Application Pre-examination Publication No.
JP-A-04-119013 proposes a structure of a coding system configured to realize a high-speed real-time processing adapted to a high quality moving picture, by use of hardware, without making the circuit construction so complicated. This system uses an event memory for independently executing an event generation and an insertion of another added code for coding the DCT coefficient, thereby to realize a high speed coding processing.
FIG. 1 is a block diagram illustrating the prior art variable length coding system. In FIG. 1, Reference Numeral 201 designates an event generator receiving a quantized DCT coefficient for converting it into an event composed of a combination of the number of continuing 0s in a coefficient and a non-zero value following the continuing 0s in the coefficient, and Reference Numeral 202 denotes an event memory for temporarily storing the event thus obtained. Reference Numeral 203 indicates a code generation pre-processing unit for executing a pre-processing necessary for allocating the variable length code for the event, and Reference Numeral 204 shows a code table for allocating the variable length code for the event. Reference Numeral 205 designates a switching circuit, and Reference Numeral 206 designates a packing circuit for re-arranging the variable length code into a string of continuous bits
In this example, first, the event of coefficient data corresponding to one block is generated. Namely, if an input is "0", the event generator 201 increments a counter counting the number of continuing 0s in the coefficient. If the input is a non-zero value, the event generator 201 records the number of continuing 0s and the non-zero value following the continuing 0s in the coefficient, in the event memory 202 as a set of events. In addition, the event counter 201 reset the counter counting the number of continuing 0s. This processing is repeated, and all the events corresponding to the one block are written into the event memory 202. Incidentally, a bit for discriminating the addition of "EOB" (end of block) is added to the event, and this bit is made to "ON" at the end of the block.
Then, the events written in the event memory 202 are read out in sequentially, and a code corresponding to the read-out event is generated. Prior to this processing, in the pre-processing unit, when the bit for discriminating the addition of "EOB" is "ON", an event for indicating the coding of the EOB is additionally generated.
Furthermore, the code generation pre-processing unit 203, the pre-processed event is supplied as an address for the code table 204, so that a corresponding code word of the variable length code and its code length are outputted from the code table.
In the switching circuit 205, the above processed code of the variable length code and its other adding codes are selected, and the adding code is inserted in accordance with a syntax.
Finally, in the packing circuit 206, a drain of bits continuing from an input sign is constructed.
As a prior art method for reducing the size of the variable length code table, methods disclosed in for example Japanese Patent Application Pre-examination Publication No. JP-A-04-142163 and No. JP-A-08-079091 have been known.
In the variable length coding system disclosed in JP-A-04-142163, since more significant bits of the code word of the variable length code have a feature that there is high possibility that a pattern of the same code is repeated, the code words stored in the variable length code table are represented by the length of the pattern repeating the same bit and the remaining code, as shown in FIG. 2.
According to the representation, in order to represent the code of the DCT coefficients of the MPEG (Moving Picture Experts Group) 1, 4 bits are used for representing the repetition number, and 6 bits are used for the remaining data. Furthermore, 4 bits are used for represent the code length, and therefore, the length of the whole is represented by 14 bits per one code.
In the system disclosed by JP-A-08-079091, the code is classified into four classes in accordance with the range of coefficient value (level). The address of the variable length code table corresponding to a combination of the number (or run) of continuing 0s in the coefficient and the level, is constituted of the fixed length as a whole, which includes a flag region discriminated in accordance with the class, a region indicative of the run, and a region indicative of the level. The sizes of the run region and the level region are determined to a minimum size required to store a maximum value included in the respective classes. For example, in order to represent the code of the DCT coefficients of MPEG1, 11 bits are used in the example shown in FIG. 3.
However, the above mentioned prior art systems have the following problems:
A first problem is that, in the above mentioned prior art system using the event memory, a memory capacity larger than the coefficient data is necessary.
The reason for this is that; Since the event memory must comply with occurrence of a maximum event number, the event memory is required to have a memory capacity capable of storing the events of the number at least equal to the number of coefficient data items. In addition, since it is necessary to record the zero run information and the EOB flag in addition to the non-zero coefficient value, the bit width required for one event becomes larger than the coefficient data.
A second problem is that, when many effective coefficients are generated, the advantage of a high speed processing attributable to a parallel processing cannot be obtained or is broken down.
The reason for this is that: When many effective coefficients are generated, and therefore, when the number of events becomes large, even if the event generating processing is executed in the course of a process for inserting the adding data, the number of code words to be coded including the adding data often becomes larger than the number of the input DCT coefficients. In addition, the writing and the reading of the event cannot be executed simultaneously, if the number of events becomes large, there is possibility that the coding processing for one block has not been completed during one block period.
A third problem is that a real time processing cannot be guaranteed.
The reason for this is that: Since the event memory is used, a delay from the inputting of the DCT coefficients to the outputting of the corresponding code is not at constant. In addition, since the writing and the reading of the event cannot be executed simultaneously, if the number of events becomes large, there is possibility that the delay becomes large.
A fourth problem is that, whether or not the coding processing for the event is ceaselessly executed at a fixed delay, is indefinite.
The reason for this is that: Only the variable length coding processing with reference to the code table is prepared, but neither the fixed length coding processing for the fixed length code such as the escape code, nor the processing for the intra-DC component is prepared.
A fifth problem is that, the above mentioned prior art system for reducing the size of the variable length code table is not sufficient to reduce the size of the variable length code table.
The reason for this is that: In the method for recording the repetition number of the same bit, the memory is used even for recording the repetition number, and therefore, the reduction of the bit width of the code word is not sufficient. In addition, with classification based on only the level, there still exist many invalid regions in which an address is defined for a combination of the run and the level for which a variable length code is not allocated.